package leetCode.q56;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }

        //按照起点位置排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> res = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            //对于每条范围，取左右端点
            int L = intervals[i][0], R = intervals[i][1];

            if (res.size() == 0 || L > res.get(res.size() - 1)[1]) {//空或者左端点在最后一条之后
                res.add(new int[]{L, R});
            } else {
                //更新右端点
                res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], R);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}
